The present invention relates to shadowing methods and apparatus, and more particularly to methods and apparatus for shadowing using a depth buffer algorithm to provide a three dimensional expression of a picture as a whole.
In the field of computer graphics, development in expression is demanded. Concretely it is strongly demanded that not only three dimensional expression of an unit figure but also three dimensional expression of all figures as a whole is carried out. To satisfy the demand, research has been directed to carrying out a shadowing function for performing the three dimensional expression of all figures as a whole in a computer graphics system.
Following are proposals for shadowing:
(1) A first method (refer to FIG. 12) includes the steps of. PA0 (2) A second method (refer to FIG. 13) includes the steps of, PA0 (3) A third method includes the steps of,
imaging viewing direction line segments for uniting a viewpoint and points on a projection plane which points correspond to each pixel, PA1 obtaining crossing points of each viewing direction line segment and the frontmost figure intersecting the viewing direction line segment, PA1 obtaining light beam direction line segments for uniting a light source and each crossing point, PA1 determining the existence of figures which intersect the light beam direction line segments, PA1 drawing the crossing points as shadowed only when at least one figure exists which intersects the light beam direction line segment. PA1 projecting edges of any polygon onto another polygon, PA1 projecting the projected edges onto a projection plane, PA1 obtaining a shadowed region of a scan line based on the result on the projection plane. PA1 obtaining shadowed regions by applying an algorithm the same as the hidden surface removal to each figure supposing the depth direction as seen from the light source (refer to FIG. 14(A)), PA1 applying hidden surface removal to each figure supposing the depth direction as seen from the viewpoint, and mapping the shadow regions onto a projection plane (refer to FIG. 14(B)).
The first method requires a simple algorithm to display figures with shadow. But the disadvantage of requiring a long period of time for the shadowing operation arises because such operations are repeatedly carried out for every pixel.
The second method has a shortened time period compared with the first method because the shadowing operation is carried out for every scan line instead of every pixel. There is still the disadvantage that the time period is still not sufficiently shortened.
In both methods, when the figure is a freely curved surface, described by a pair cubical parametric equations, remarkably long time periods for calculation are required. As a result a remarkably long time period is required for shadowing.
The third method shortens the time period compared with the first and the second methods because the shadow regions are obtained by the algorithm used for hidden surface removal. This method has the disadvantage mapping operations are necessary which require more data and longer processing time. Also the time period is still not sufficiently short because every pixel is subjected to a shadowing operation. A further disadvantage is that figures applicable to a shadowing operation are limited because of a need for determining the relationship between figures.
Considering these disadvantages, a shadowing method is disclosed which applies a depth buffer algorithm to figures defined in both a light source coordinate system and a view reference coordinate system. Refer to "Simplified shadowing method with Z-buffer method" by Shimizu Kazuya and three others, the 30th national convention of data processing society (the first term of Showa 60-nen).
The method does not consider a limit for shadowing, useless shadowings are carried out and insufficient shadowing accuracy is obtained corresponding to a region necessary for shadowing, accordingly. Also coordinate transformations, comparison between coordinate values and others necessary for shadowing are carried out for each pixel, quantity of calculation is increased remarkably and useless calculation is carried out, accordingly. As a result, disadvantages in insufficiently reduced time periods for shadowing arise.
More particularly, the Shimizu Kazuya et al. method can be divided into two groups of operations, one group of operations involves extracting the most light source side depth values in the light source coordinate system, and the other group of operations involves calculating intensity values of every pixel based on the comparison results of depth values of every figure in the light source coordinate system when executing interpolation in the view reference coordinate system. The former group of operations is carried out with hardware like symmetric digital differential analyzers (hereinafter referred to as DDA) so as to operate at extremely high speed, the necessary time for unit operation is on the order of nsec. or tens of nsec. Sufficient shortening of time is accordingly achieved. On the contrary, the latter group of operations is carried out with software because comparing operations and calculating operations based on the comparison result are not suitably carried out with hardware. As a result, the latter group of operations is carried out at extremely low speed compared with the former group of operations, and the necessary time for unit operation is on the order of microseconds when using a popular computer graphic system. Further, the latter group of operations must be carried out for every pixel of every figure, and the disadvantage of insufficiently shortened shadowing time arises.
Furthermore, every method described in the foregoing applies to a model having only one light source, and does not apply &o plural light sources. In most real life situations, the model has plural light sources. It seems possible that the Shimizu Kazuya et al. method are applicable to a model having plural light sources, but it is practically impossible because the method requires plural depth buffers, each having large storing capacity.